package com.peng.leetcode.heap;

import java.util.PriorityQueue;

/**
 * ReorganizeString
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 *
 * @author: lupeng6
 * @create: 2020/12/11 21:23
 */
public class ReorganizeString {

    public static void main(String[] args) {
        String str = "aab";
        str = new Solution().reorganizeString(str);
        System.out.println(str);

//        System.out.println(Character.valueOf((char) ((char) 1 + 'a')));
    }

    static class Solution {
        public String reorganizeString(String str) {
            int[] counts = new int[26];
            for (char c : str.toCharArray()) {
                counts[c - 'a']++;
            }

            PriorityQueue<int[]> maxHeap = new PriorityQueue<>((c1, c2) -> c2[1] - c1[1]);

            for (int i = 0; i < counts.length; i++) {
                if (counts[i] > 0) {
                    maxHeap.offer(new int[]{i, counts[i]});
                }
            }

            StringBuilder builder = new StringBuilder();
            while (maxHeap.size() > 1) {
                int[] first = maxHeap.poll();
                int[] second = maxHeap.poll();
                builder.append((char) ((char) first[0] + 'a'));
                builder.append((char) ((char) second[0] + 'a'));
                if (first[1] > 1) {
                    maxHeap.offer(new int[]{first[0], first[1] - 1});
                }
                if (second[1] > 1) {
                    maxHeap.offer(new int[]{second[0], second[1] - 1});
                }
            }
            if (!maxHeap.isEmpty()) {
                int[] last = maxHeap.poll();

                if (last[1] > 1) {
                    return "";
                }

                builder.append((char) ((char) last[0] + 'a'));
            }

            if (!maxHeap.isEmpty()) {
                return "";
            }

            return builder.toString();
        }
    }
}
